import java.util.Arrays;

/**
 * @author 刘学松
 * @date 2023-08-17 16:19
 */
public class KMP {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(prefix("abcabcab")));
    }
    /**
     * 前缀函数
     * @param word
     * @return
     */
    public static int[] prefix(String word) {
        int len = word.length();
        int[] f = new int[len];
        for (int i = 1; i < len; i++) {
            int j = f[i - 1];
            while (j > 0 && word.charAt(i) != word.charAt(j)) {
                j = f[j - 1];
            }
            if (word.charAt(i) == word.charAt(j)) {
                j++;
            }
            f[i] = j;
        }
        return f;
    }
}
